package com.acwing.lc.part1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author rkc
 * @date 2022/9/17 11:05
 */
public class LC68文本左右对齐 {

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            int j = i + 1, len = words[i].length();
            //如果能放下下一个单词和一个间隔符的空格，就继续放
            while (j < words.length && len + words[j].length() + 1 <= maxWidth) {
                len = len + words[j].length() + 1;
                j++;
            }
            StringBuilder line = new StringBuilder(words[i]);
            if (j == words.length || j == i + 1) {
                //说明要么全部单词都可以放在一行，要么只有当前的words[i]能放在这一行，选择左对齐
                for (int k = i + 1; k < j; k++) line.append(' ').append(words[k]);
                while (line.length() < maxWidth) line.append(' ');
            } else {
                //左右对齐，cnt表示单词之间间隙的空格数，space表示分割需要的所有空格数
                int cnt = j - i - 1, space = maxWidth - len + cnt;
                int k = 0;
                //有 space % cnt 个间隙需要多一个空格
                while (k < space % cnt) {
                    line.append(repeat(' ', space / cnt + 1)).append(words[i + k + 1]);
                    k++;
                }
                while (k < cnt) {
                    line.append(repeat(' ', space / cnt)).append(words[i + k + 1]);
                    k++;
                }
            }
            ans.add(line.toString());
            i = j - 1;
        }
        return ans;
    }

    private String repeat(char c, int cnt) {
        char[] arr = new char[cnt];
        Arrays.fill(arr, c);
        return new String(arr);
    }
}
